/*
 *  SMForwardGraph.c
 *  Seams
 *
 *  Created by Charles Osmer on 4/21/09.
 *  Copyright 2009 __MyCompanyName__. All rights reserved.
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "SMForwardGraph.h"

//#define DebugAssert(e) assert(e)
#define DebugAssert(e)

#define UNMASKED 0

#pragma mark Graph Lifespan

const SMForwardGraph SMForwardGraph_Initializer = {NULL, NULL, 0};

void SMForwardGraph_Alloc(SMForwardGraph *graph, const SMImage *image)
{
    assert(graph != NULL);
    assert(graph->nodes == NULL);
    SMImageAssert(image);

    graph->image = image;
    graph->nodes = calloc(image->width*image->height, sizeof(SMForwardGraphNode));

    graph->nSeams = 0;

    SMImage intensity = SMImage_RGB2Gray(image);
    for (int i=0; i < intensity.width*intensity.height; i++) {
        const int x = i % intensity.width;
        const int y = i / intensity.width;

        graph->nodes[i].value = intensity.planes[0][y][x];
    }
    SMImage_Free(&intensity);

    SMForwardGraph_ResetGraph(graph);
}

void SMForwardGraph_Free(SMForwardGraph *graph)
{
    SMGraphAssert(graph);

    graph->image = NULL;
    free(graph->nodes);
    
    graph->nSeams = 0;
}

#pragma mark -
#pragma mark Graph Operations

#define nodeAt(x,y,w)   (((y)*(w))+(x))

void SMForwardGraph_ResetGraph(SMForwardGraph *graph)
{
    SMGraphAssert(graph);
    
    const int w = graph->image->width;
    const int h = graph->image->height;
    
    for (int y=0; y < h; y++) {
        for (int x=0; x < w; x++) {
            SMForwardGraphNode *node = &(graph->nodes[nodeAt(x, y, w)]);

            node->left  = (x == 0   ? NULL : &(graph->nodes[nodeAt(x-1, y, w)]));
            node->right = (x == w-1 ? NULL : &(graph->nodes[nodeAt(x+1, y, w)]));

            node->up   = (y == 0   ? NULL : &(graph->nodes[nodeAt(x, y-1, w)]));
            node->down = (y == h-1 ? NULL : &(graph->nodes[nodeAt(x, y+1, w)]));

            node->cost = 0;
            node->seamEdge = NULL;

            node->maskLevel = UNMASKED;
        }
    }
    
    graph->nSeams = 0;
}

static void SMForwardGraph_MaskSeam(SMForwardGraph *graph, const SMForwardGraphNode *firstNode, const unsigned int maskLevel)
{
    SMGraphAssert(graph);
    assert(firstNode != NULL);

    SMForwardGraphNode *node = (SMForwardGraphNode *)firstNode;
    while (node != NULL) {
        DebugAssert(node->maskLevel == UNMASKED);
        node->maskLevel = maskLevel;

        if (node->left != NULL) {
            node->left->right = node->right;

            if (node->left->down == node->seamEdge && node->left->down != NULL) {
                node->left->down = node->down;
                node->down->up = node->left;
            }
        }

        if (node->right != NULL) {
            node->right->left = node->left;
            
            if (node->right->down == node->seamEdge && node->right->down != NULL) {
                node->right->down = node->down;
                node->down->up = node->right;
            }
        }

        node = node->seamEdge;
    }

    ++graph->nSeams;
}

SMImage SMForwardGraph_CarveImage(const SMForwardGraph *graph, const unsigned int level)
{
    SMGraphAssert(graph);
    assert(level <= graph->nSeams);

    const SMImage *sourceIm = graph->image;

    SMImage carvedIm = SMImage_Initializer;
    SMImage_Alloc(&carvedIm, sourceIm->nPlanes, sourceIm->width-level, sourceIm->height);

    for (int p=0; p < sourceIm->nPlanes; p++) {
        for (int i=0, k=0; i < sourceIm->width*sourceIm->height; i++) {
            if (graph->nodes[i].maskLevel != UNMASKED && graph->nodes[i].maskLevel <= level)
                continue;

            const int x = i % sourceIm->width;
            const int y = i / sourceIm->width;

            const int mx = k % carvedIm.width;
            const int my = k / carvedIm.width;

            carvedIm.planes[p][my][mx] = sourceIm->planes[p][y][x];
            ++k;
        }
    }
    
    return carvedIm;
}

#pragma mark -
#pragma mark Seam Carving

static SMForwardGraphNode *SMForwardGraph_MinimizeGraph(SMForwardGraph *graph)
{
    const int w = graph->image->width;
    const int h = graph->image->height;

    for (int i=w*(h-1)-1; i >= 0; i--) {
        SMForwardGraphNode *thisNode = &(graph->nodes[i]);
        if (thisNode->maskLevel > 0)
            continue;
        
        const unsigned int u = (thisNode->up    == NULL ? 0 : thisNode->up->value);
        const unsigned int l = (thisNode->left  == NULL ? 0 : thisNode->left->value);
        const unsigned int r = (thisNode->right == NULL ? 0 : thisNode->right->value);
        
        const unsigned int cu = abs(r-l);
        const unsigned int cl = cu + abs(u-l);
        const unsigned int cr = cu + abs(u-r);

        SMForwardGraphNode *down = thisNode->down;
        
        SMForwardGraphNode *minNode = down;
        unsigned int minCost = down->cost + cu;

        if (down->left != NULL) {
            const unsigned int cost = down->left->cost + cl;
            if (cost < minCost) {
                minNode = down->left;
                minCost = cost;
            }
        }

        if (down->right != NULL) {
            const unsigned int cost = down->right->cost + cr;
            if (cost < minCost) {
                minNode = down->right;
                minCost = cost;
            }
        }

        thisNode->cost = minCost;
        thisNode->seamEdge = minNode;
    }

    // Search top row for start of the shortest path through image
    SMForwardGraphNode *firstSeamNode = NULL;
    for (int i=0; i < w; i++) {
        if (graph->nodes[i].maskLevel > 0)
            continue;
        
        if (firstSeamNode == NULL) {
            firstSeamNode = &(graph->nodes[i]);
            continue;
        }

        if (graph->nodes[i].cost < firstSeamNode->cost)
            firstSeamNode = &(graph->nodes[i]);
    }

    return firstSeamNode;
}

int SMForwardGraph_CalculateSeams(SMForwardGraph *graph, unsigned int nMaxSeams)
{
    SMGraphAssert(graph);

    unsigned int nSeams = 0;

    SMForwardGraphNode *seamNode = NULL;
    while (nSeams < nMaxSeams) {
        seamNode = SMForwardGraph_MinimizeGraph(graph);
        if (seamNode == NULL)
            break;

        SMForwardGraph_MaskSeam(graph, seamNode, nSeams+1);
        ++nSeams;
    }

    return nSeams;
}
